#include <bits/stdc++.h>
using namespace std;

const int M = 105;
const int INF = 0x3f3f3f3f;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int m, n;
int g[M][M];
int dis[M][M];

struct Node {
    int x, y;
    int color;
    bool magic;
    int cost;
};

void init() {
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            g[i][j] = -1;
            dis[i][j] = INF;
        }
    }
}

int bfs() {
    queue<Node> q;
    
    q.push({1, 1, g[1][1], false, 0});
    dis[1][1] = 0;
    
    while (!q.empty()) {
        Node c = q.front();
        q.pop();
        
        int x = c.x, y = c.y;
        int color = c.color;
        bool magic = c.magic;
        int cost = c.cost;
        
        if (cost > dis[x][y]) continue;
        
        if (x == m && y == m) {
            continue;
        }
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx < 1 || nx > m || ny < 1 || ny > m) continue;
            
            if (magic && g[nx][ny] == -1) continue;
            
            if (g[nx][ny] != -1) {
                int nc = cost;
                
                if (color != g[nx][ny]) {
                    nc += 1;
                }
                
                if (nc < dis[nx][ny]) {
                    dis[nx][ny] = nc;
                    q.push({nx, ny, g[nx][ny], false, nc});
                }
            }
            else if (!magic && g[nx][ny] == -1) {
                int nc = cost + 2;
                
                if (nc < dis[nx][ny]) {
                    dis[nx][ny] = nc;

                    q.push({nx, ny, color, true, nc});
                }
            }
        }
    }
    
    return dis[m][m] == INF ? -1 : dis[m][m];
}

int main() {
    cin >> m >> n;
    
    init();
    
    for (int i = 0; i < n; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        g[x][y] = c;
    }
    
    int ans = bfs();
    cout << ans << endl;
    
    return 0;
}
